package com.zjj.lbw.algorithm.sort;

import java.util.Arrays;

/**
 * @author zhanglei.zjj
 * @description 快速排序
 * @date 2023/4/1 18:00
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] unsortedArr = new int[]{35, 63, 48, 9, 86, 24, 53, 11};
        quickSort(unsortedArr, 0, unsortedArr.length - 1);

        System.out.println("排序后的元素顺序为：" + Arrays.toString(unsortedArr));
    }

    static void quickSort(int[]arr, int from, int to) {
        int zoneIndex = partition(arr, from, to);
        if (zoneIndex > from) {
            quickSort(arr, from, zoneIndex - 1);
        }
        if (zoneIndex < to) {
            quickSort(arr, zoneIndex, to);
        }
    }

    static int partition(int[] arr, int from, int to) {
        // 只有一个元素无需分区
        if (from == to) {
            return from;
        }
        int pivot = (int) (from + Math.random() * (to - from + 1));

        // 将基准数和数组尾元素交换顺序
        swap(arr, pivot, arr.length - 1);

        int partitionIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= arr[arr.length - 1]) {
                partitionIndex ++;

                if (i > partitionIndex) {
                    swap(arr, partitionIndex, i);
                }
            }
        }
        return partitionIndex;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
